package main

import "fmt"

// 问题描述： 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
// 状态转移方程

func maxSubArray(nums []int) int {
	n := len(nums)
	maxSum := nums[0]
	for i := 1; i < n; i++ {
		if nums[i-1] > 0 {
			nums[i] += nums[i-1]
		}
		maxSum = max(nums[i], maxSum)
	}

	return maxSum
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	sum := maxSubArray([]int{-2, 1, -3, 4, -1, 2, 1, -5, 4})
	fmt.Println(sum)
}
